package com.bee.剑指offer;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
 * 1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
 * 2.总节点数目为n
 * 3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)
 */
public class 二叉树中和为某一值的路径3 {

    private static List<Integer> preResult = new ArrayList<>();

    private static List<List<Integer>> result = new ArrayList<>();

    private static int count = 0;

    public void preRound(TreeNode root) {
        if (root == null) {
            return;
        }
        // 这个地方可以做很多事情，例如可以对这个节点为父节点继续进行遍历子树
        preResult.add(root.val);
        preRound(root.left);
        preRound(root.right);
    }

    public int FindPath(TreeNode root, int sum) {
        if (root == null) {
            return count;
        }
        // 由于可以不从根节点开始，所以必须对每个子数进行深度遍历
        // 这里可以做很多事情，例如可以继续深度深度遍历子树
        dfs(root, sum);

        FindPath(root.left, sum);
        FindPath(root.right, sum);
        return count;
    }

    /**
     * 深度遍历子树遍历
     */
    public void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        sum -= root.val;
        if (sum == 0) {
            // 计数使用
            count++;
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }

    public static void main(String[] args) {

    }
}
